public class MissingNumber {
    //数组nums包含了从0到n的所有整数，但是少了一个
    //所以数组的实际长度为n
    //数学方法，将0到n所有的整数相加，然后逐个减去数组中的元素，结果就是缺失的数字
    public static int missingNumber1(int[] nums) {

        int n = nums.length;
        int sum = n*(n+1)/2;
        for (int i = 0; i < nums.length; i++) {
            sum-=nums[i];
        }

        return sum;
    }

    //也可以利用异或的性质，相同的数异或会抵消
    //先把0到n全部异或一遍
    //然后逐个异或数组中的元素，最终异或的结果就是缺失的那个数
    public static int missingNumber2(int[] nums) {
        int n = nums.length;
        int xor = 0;
        //注意边界条件
        for (int i = 0; i <= n; i++) {
            xor^=i;
        }

        for (int i = 0; i < nums.length; i++) {
            xor^=nums[i];
        }

        return xor;
    }

    public static void main(String[] args) {
        //预期输出为2
        int[] nums = new int[]{9,6,4,2,3,5,7,0,1};
        int missingNumber = missingNumber2(nums);
        System.out.println(missingNumber);
    }
}
